//实现红黑树
#include <iostream>
#include <utility>
#include <cassert>

typedef enum {RED, BLACK} ColorType;
template<class K, class V>
struct RBTreeNode
{
    pair<K, V> _kv;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    ColorType _col;
    RBTreeNode(const pair<K, V>& kv)
        : _kv(kv)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _col(RED)
    {}
};

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:
    RBTree()
        : _root(nullptr)
    {}
    bool Insert(const pair<K, V>& kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;
        // 更新平衡因子
        while (parent)
        {
            // 更新平衡因子
            if (cur == parent->_left)
            {
                parent->_bf--;
            }
            else
            {
                parent->_bf++;
            }
            if (parent->_bf == 0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }
            else
            {
                if (parent->_bf == 2)
                {
                    if (cur->_bf == 1)
                    {
                        RotateL(parent);
                    }
                    else
                    {
                        RotateRL(parent);
                    }
                }
                else
                {
                    if (cur->_bf == -1)
                    {
                        RotateR(parent);
                    }
                    else
                    {
                        RotateLR(parent);
                    }
                }
                break;
            }
        }
        _root->_bf = 0;
        return true;
    }
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }
protected:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;
        if (parent == _root)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = subR;
            }
            else
            {
                ppNode->_right = subR;
            }
            subR->_parent = ppNode;
        }
        parent->_bf = subR->_bf = 0;
    }
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subL;
        if (parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
        parent->_bf = subL->_bf = 0;
    }
    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);
        if (bf == -1)
        {
            subL->_bf = 0;
            parent->_bf = 1;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            parent->_bf = 0;
        }
        else
        {
            subL->_bf = 0;
            parent->_bf = 0;
        }
        subLR->_
        bf = 0;
    }
    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 0)
        {
            subR->_bf = 0;
            parent->_bf = 0;
        }
        else if (bf == 1)
        {
            subR->_bf = -1;
            parent->_bf = 0;
        }
        else
        {
            subR->_bf = 0;
            parent->_bf = 1;
        }
        subRL->_bf = 0;
    }
    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << " ";
        _InOrder(root->_right);
    }
private:
    Node* _root;
};

//测试红黑树
void TestRBTree()
{
    RBTree<int, int> t;
    t.Insert(make_pair(16, 1));
    t.Insert(make_pair(3, 1));
    t.Insert(make_pair(7, 1));
    t.Insert(make_pair(11, 1));
    t.Insert(make_pair(9, 1));
    t.Insert(make_pair(26, 1));
    t.Insert(make_pair(18, 1));
    t.Insert(make_pair(14, 1));
    t.Insert(make_pair(15, 1));
    t.Insert(make_pair(21, 1));
    t.Insert(make_pair(22, 1));
    t.Insert(make_pair(23, 1));
    t.Insert(make_pair(24, 1));
    t.Insert(make_pair(25, 1));
    t.Insert(make_pair(30, 1));
    t.Insert(make_pair(28, 1));
    t.Insert(make_pair(41, 1));
    t.Insert(make_pair(47, 1));
    t.Insert(make_pair(40, 1));
    t.Insert(make_pair(38, 1));
    t.Insert(make_pair(39, 1));
    t.Insert(make_pair(37, 1));
    t.Insert(make_pair(36, 1));
    t.Insert(make_pair(35, 1));
    t.Insert(make_pair(34, 1));
    t.Insert(make_pair(33, 1));
    t.Insert(make_pair(32, 1));
    t.Insert(make_pair(31, 1));
    t.Insert(make_pair(29, 1));
    t.Insert(make_pair(27, 1));
    t.Insert(make_pair(20, 1));
    t.Insert(make_pair(19, 1));
    t.Insert(make_pair(17, 1));
    t.Insert(make_pair(13, 1));
    t.Insert(make_pair(12, 1));
    t.Insert(make_pair(10, 1));
    t.Insert(make_pair(8, 1));
    t.Insert(make_pair(6, 1));
    t.Insert(make_pair(5, 1));
    t.Insert(make_pair(4, 1));
    t.Insert(make_pair(2, 1));
    t.Insert(make_pair(1, 1));
    t.InOrder();
}
int main()
{
    TestRBTree();
    return 0;
}

